package algorithm;

import java.util.Arrays;
import java.util.Random;

public class Knapsack {
	static Random random = new Random();
	static int length = random.nextInt(9) + 1;
	static int weight = (random.nextInt(90) + 10) * (random.nextInt(9) + 1);
	
	public static void main(String[] args) {
		
		int[] v = new int[length];
		int[] w = new int[length];
		int i;
		for (i = 0; i < length; i++) {
			w[i] = random.nextInt(90) + 10;
			v[i] = w[i] * (random.nextInt(9) +1);
		}
		System.out.println("the vale and weigth:");
		System.out.print("v:"); print(v);
		System.out.print("w:"); print(w);
		
		System.out.println("the length: " + length + "\nthe weigth: " + weight);
		System.out.println("The result of 0-1 knapsack with dynamic method is:" + dynamic01Knapsack(v,w,length,weight));
		System.out.println("The result of part knapsack with greedy method is:" +greedyPartKnapsack(v,w,length,weight));
		
		/*
		int[] v = {60,100,120};
		int[] w = {10,20,30};
		
		System.out.println(dynamic01Knapsack(v,w,3,50));
		System.out.println(greedyPartKnapsack(v,w,3,50));
		*/
		/*
		int[] v = {153,78,72,177,186,72};
		int[] w = {61,39,36,59,31,24};
		System.out.println("the vale and weigth:");
		print(v);
		print(w);
		
		System.out.println("the length: " + 6 + "\nthe weigth: " + 180);
		System.out.println("The result of 0-1 knapsack with dynamic method is:" + dynamic01Knapsack(v,w,6,180));
		System.out.println("The result of part knapsack with greedy method is:" +greedyPartKnapsack(v,w,6,180));
		*/
	}
	
	private static int dynamic01Knapsack(int[] v, int[] w, int n, int W) {
		int[][] c = new int[n+1][W+1];
		int i,j;
		
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= W; j++) {
				if(w[i-1] <= j) {
					if (v[i-1] + c[i-1][j-w[i-1]] > c[i-1][j]) {
						c[i][j] = v[i-1] + c[i-1][j-w[i-1]];
					} else {
						c[i][j] = c[i-1][j];
					}
				} else {
					c[i][j] = c[i-1][j];
				}
			}
		}
		return c[n][W];
	}
	private static class Node implements Comparable<Node> {
		int v;
		int w;
		int k;
		
		public Node(int v, int w, int k) {
			this.v = v;
			this.w = w;
			this.k = k;
		}

		@Override
		public int compareTo(Node o) {
			return o.k - this.k;
		}
	}
	private static int greedyPartKnapsack(int[]v, int[] w, int n, int W) {
		int i, value = 0;
		Node[] arr = new Node[n];
		for (i = 0; i < n; i++) {
			arr[i] = new Node(v[i], w[i], v[i]/w[i]);
		}
		Arrays.sort(arr);
		for (i = 0; i < n; i++) {
			if (arr[i].w <= W ) {
				value += arr[i].v;
				W -= arr[i].w;
			} else {
				value += arr[i].v * W / arr[i].w;
				break;
			}
		}
		return value;
	}
	
	private static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.printf(" %3d",arr[i]);
		}
		System.out.println();
	}
}
